// BF_Queue.h: interface for the CBF_Queue class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_BF_QUEUE_H__2F2470E8_F0D3_4861_9482_D5EC196EEC7B__INCLUDED_)
#define AFX_BF_QUEUE_H__2F2470E8_F0D3_4861_9482_D5EC196EEC7B__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <functional>
#include <atomic>

#ifdef _WINDOWS
#define CAS(a_ptr, a_oldVal, a_newVal) InterlockedCompareExchange(a_ptr, a_newVal, a_oldVal)
#else
#define CAS(a_ptr, a_oldVal, a_newVal) __sync_bool_compare_and_swap(a_ptr, a_oldVal, a_newVal)

#endif

typedef unsigned long long UINT64_;

template <typename ELEM_T, UINT64_ Q_SIZE, bool onepush = false>
class CBF_QueueNoLock
{
public:
    CBF_QueueNoLock()
    {
        m_writeIndex = 0;
        m_readIndex = 0;
        m_maximumReadIndex = 0;
        m_count = 0;
    }
    virtual ~CBF_QueueNoLock()
    {
    }

    UINT64_ size()
    {
        return m_count;
    }
    // 放入数据至无锁队列
    bool Push(const ELEM_T &a_data)
    {
        UINT64_ currentWriteIndex; // 获取写指针的位置
        UINT64_ currentReadIndex;
        //       int curtms = CBF_Date_Time::GetTickCount();
        // 1. 获取可写入的位置
        bool bret = false;
        while (!bret)
        {
            currentWriteIndex = m_writeIndex;
            currentReadIndex = m_readIndex;
            if (countToIndex(currentWriteIndex + 1) == countToIndex(currentReadIndex))
            {
                // 队列满
                return false;
            }
            UINT64_ res = CAS(&m_writeIndex, currentWriteIndex, (currentWriteIndex + 1));
#ifdef _WINDOWS
            if (res == currentWriteIndex)
            {
                break;
            }
#else
            if (res == 1)
            {
                break;
            }
#endif
            // 目的是为了获取一个能写入的位置
        }
        // 获取写入位置后 currentWriteIndex 是一个临时变量，保存我们写入的位置
        m_thequeue[countToIndex(currentWriteIndex)] = a_data; // 把数据更新到对应的位置
        if (onepush)
        {
            m_maximumReadIndex++;
        }
        else
        {

            // 2. 更新可读的位置，按着m_maximumReadIndex+1的操作
            bret = false;
            while (!bret)
            {
                UINT64_ res = CAS(&m_maximumReadIndex, currentWriteIndex, (currentWriteIndex + 1));
#ifdef _WINDOWS
                if (res == currentWriteIndex)
                {
                    break;
                }
#else
                if (res == 1)
                {
                    break;
                }
#endif
                // 走到下面是因为后面的在更新，所以要切换线程，等待做完再做
#ifdef _WINDOWS
                Sleep(0); // 切换到同优先级的线程或高优先级的线程
#else
                sched_yield(); // 先在当前线程所在的核心上遍历合适的任务线程，如果有的话，就切换到该线程
#endif
            }
        }
        m_count++;
        return true;
    }
    // 从无锁队列取出一条数据
    bool Pop(ELEM_T &a_data)
    {
        UINT64_ currentMaximumReadIndex;
        UINT64_ currentReadIndex;
        while (true)
        {
            currentReadIndex = m_readIndex;
            currentMaximumReadIndex = m_maximumReadIndex;

            if (countToIndex(currentReadIndex) == countToIndex(currentMaximumReadIndex)) // 如果不为空，获取到读索引的位置
            {
                return false;
            }
            // retrieve the data from the queue
            a_data = m_thequeue[countToIndex(currentReadIndex)]; // 从临时位置读取的
            UINT64_ res = CAS(&m_readIndex, currentReadIndex, (currentReadIndex + 1));
#ifdef _WINDOWS
            if (res == currentReadIndex)
            {
                m_count--;
                return true;
            }
#else
            if (res == 1)
            {
                m_count--;
                return true;
            }
#endif
            // 说明这个数据已经被别人读走了，重新开始
        }
        return false;
    }

private:
    ELEM_T m_thequeue[Q_SIZE]; // 数组，存放数据
    std::atomic<UINT64_> m_count;
    volatile UINT64_ m_writeIndex; // 写的数据计数

    volatile UINT64_ m_readIndex; // 读的数据计数

    volatile UINT64_ m_maximumReadIndex; // 最大的数据记数，即队尾

    // 根据计数，获取对应的数组下标
    inline UINT64_ countToIndex(UINT64_ a_count) //
    {
        return a_count % Q_SIZE;
    }
};

#endif // !defined(AFX_BF_QUEUE_H__2F2470E8_F0D3_4861_9482_D5EC196EEC7B__INCLUDED_)
